import java.util.ArrayList;
import java.util.List;

public class Insert {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> temp = new ArrayList<>();
        boolean flag = false;
        for (int i = 0; i < intervals.length; i++) {
            if (flag) {
                temp.add(new int[]{intervals[i][0], intervals[i][1]});
                continue;
            }
            if (end < intervals[i][0]) {
                temp.add(new int[]{start, end});
                temp.add(new int[]{intervals[i][0], intervals[i][1]});
                flag = true;
            } else if (start <= intervals[i][1]) {
                start = Math.min(intervals[i][0], start);
                end = Math.max(end, intervals[i][1]);
            } else {
                temp.add(new int[]{intervals[i][0], intervals[i][1]});
            }
        }
        if (!flag) {
            temp.add(new int[]{start, end});
        }
        return temp.toArray(new int[temp.size()][]);
    }
}
